1. Field of the Invention
This invention relates to arithmetic implementations and, more particularly, to adder circuits and methods.
2. Description of the Related Art
Computing devices typically employ one or more types of processing machines. For example, a computer may include a variety of processing machines such as central processing unit (CPU), which is often referred to as a microprocessor or just processor. In addition, a computer may include a graphics engine for generating digital images for display. Other types of processing machines include digital signal processors (DSP) and specialized cryptographic processing engines, for example.
Each of the processing machines discussed above may include one or more arithmetic circuits for performing addition. These types of arithmetic circuits are commonly referred to as adders. One common addition method is a carry look-ahead method. The circuit implementation of that method is referred to as a carry look-ahead adder. As shown below, two six-bit binary numbers, including a carry-in bit, are added to form a seven-bit sum.
                                                                                                                                                                                                                                                                  C          0                                                                                    A          5                                      A          4                                      A          3                                      A          2                                      A          1                                      A          0                                    +                              B          5                                      B          4                                      B          3                                      B          2                                      B          1                                      B          0                                                                                  ⁢                      S            6                                                                                ⁢                      S            5                                                                                ⁢                      S            4                                                                                ⁢                      S            3                                                                                ⁢                      S            2                                                                                ⁢                      S            1                                                                                ⁢                      S            0                                                                    
Using a carry look-ahead adder 10, a generate bit (e.g, G0) and a propagate bit (P0) are created for each column (bit position) of the binary numbers to be added. Thus, the generate and propagate bit pairs are referred to herein as having a given oredered position. For example, G0P0 may occupy the least significant position whle G5P5 may occupy the most significant position. The generate bit and propagate bit pairs may be combined in a variety of ways, depending on the specific logic implementation, by a carry creation unit 100 to create and output a carry-in bit that corresponds to each column. Similar to the generate and propagate bit pairs, the carry-in bits output by carry creation unit 100 (e.g., C1–C6) are also referred to herein as having a given ordered position. For example, C1 may occupy the least significant position while C6 may occupy the most significant position.
Generally speaking, a given carry-in bit (e.g., C1–C6) may be created based on all generate and propagate bit pairs occupying less significant ordered positions. For example, carry-in bit C1 may be created based upon the G0P0 bit pair and the C0 carry-in bit, which functions as a generate bit for the −1 position. Likewise, the C4 carry-in bit may be created based upon the G3P3 bit pair as well as the G2P2, G1P1 and G0P0 bit pairs and the C0 carry-in bit. The carry creation general equation may be written as:Ci+1=Gi+PiCi where Gi=AiBi and Pi=Ai+Bi.To further illustrate the dependency of a carry bit upon the generate and propagation bits having less significant ordered positions, the carry-in bit C4 may be written generally as:C4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0 
To start the creation of the sum bits S0–S6, while the generate and propagate signals are working through carry creation unit 100, an XOR operation is performed on the two input bits (e.g., Ai and Bi) for each column. When the respective carry-in bits are output from carry creation unit 100, another XOR operation is performed on the result of the input bit XOR operation and the carry-in bit (Ci) for that column, which results in a sum bit (Si) for that column. Thus, the summation general equation may be written as:Si=(Ai⊕Bi)⊕Ci.
In the example described above, two six-bit numbers were added. To increase the number of bits in each binary number to be added, it is possible to increase both the number of inputs and the number of outputs of carry creation unit 100. However, to do so will increase the number of logic gates within carry creation unit 100. Since increasing the number of gates may increase the area consumed on an integrated circuit chip, the cost of increasing the number of gates may become prohibitive. In addition, to add two 12-bit numbers, which is a linear increase in bits, the number of gates in the carry creation unit may incur a greater than linear increase (e.g., n log n). Also, by increasing the size of carry creation unit 100, the wire lengths may also increase, possibly causing additional unwanted delays. Further, the increase in the number of gates may also increase the number of gates in the longest path in carry creation unit 100, possibly resulting in further delays.